package Offer;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author lakersUp
 * @Classname  MedianFinder
 * @Description  数据流中的中位数, 使用大小顶堆,大顶堆保存娇小的一半,小顶堆保存较大的一半.
 * @Date 2022/2/26 15:00
 * @Version 1.0
 */
public class Offer41MedianFinder {

    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    public Offer41MedianFinder() {
        minHeap=new PriorityQueue<>();
        maxHeap=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
    }

    public void addNum(int num) {
        //大小不同添加右边(min),大小相同添加左边
        //先添加谁,谁的大小就不变,开始两者大小都是零,所以先添加的左边(大顶堆),所以最终为奇数时右边会多一个.
        if(maxHeap.size()!=minHeap.size()){
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        }else {
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }
    }

    public double findMedian() {
        if(maxHeap.size()!=minHeap.size()){
            return minHeap.peek();
        }
        return (maxHeap.peek()+minHeap.peek())/2.0;
    }
}
